\section{Proposed timeline and plan}
\label{sec:plan}

\begin{center}
\begin{tabular}{| l | p{4.5in} |}
  \hline 
  May-July, 2011 & Proposal defense, work on open problems in Section
  \ref{sec:diffusiontime-resource} and \ref{sec:diffusiontime-adversary} . \\ 
  \hline
  June-August, 2011 & Work on open problems in Section
  \ref{sec:behavioral}. If time permits, I will try open problems in
  Section \ref{sec:optimization} and Section \ref{sec:decentralized}. \\
  \hline
  August-November, 2011 & Consider any manageable open questions that come up while writing the final thesis. \\
  \hline
  December & Tentative defense date. \\
  \hline
\end{tabular}
\end{center}

\subsection{Plan}
Existing, published results (the majority of which are listed in the
``Our results'' sections of this proposal) will make up the core of my
thesis. There are some open problems in Section
\ref{sec:diffusiontime-resource} and \ref{sec:diffusiontime-adversary}
that I think I can solve between May and July. I plan to first work on
proving both triangulation process and 2-hop random walk process
complete in $O(n\log n)$ time. Then I will work on proving {\sc
  RandomForward} algorithm (defined in Section
\ref{sec:diffusiontime-adversary}) can complete in $O(n\log n)$
time. Along with the analysis on {\sc PriorityForward} algorithm (also
defined in Section \ref{sec:diffusiontime-adversary}), this will give
us some insight on the role of randomness in adversary networks. If
time permits, I'd like to try some other open problems in the same
section, like communication complexity lower bound for Line
\ref{alg:rforward-diff} in Algorithm \ref{alg:rforward}.

Next, I'd like to spend some time focusing on open problems in Section
\ref{sec:behavioral}. We have some game theoretic results on
intervention strategies (in Section \ref{sec:optimization} and
\ref{sec:decentralized}), but little has been done on the effects of
behavior changes. We already observed that the perverse outcome (shown
in Figure \ref{fig:mh}) is widespread across a range of networks; it
would be nice if we can nail down the rigorous proofs for some general
families of graphs, e.g. preferential attachment graphs and
locally-finite infinite graphs. We also observe in the simulation that
randomly picked intervention can be better than targeted strategies in
preferential attachment graphs. I will think about how to
mathematically prove our observations. And I will take some time to
develop more simulations to cover a wider range of parameters and
different families of graphs, to confirm our findings in more broader
settings. If I still have time left, I will look at the open problems
in Section \ref{sec:optimization} and \ref{sec:decentralized}.

Finally, I've left three months for following up on loose ends and
assembling the thesis by the end of November.
